本文整理自：《垃圾回收算法手册：自动内存管理的艺术》
作者：Richard Jones、Antony Hosking、Eliot Moss

引言

几乎所有的现代编程语言都使用动态内存分配(allocation),即允许进程在运行时分配或者释放无法在编译期确定大小的对象,且允许对象的存活时间超出创建这些对象的子程序时间。动态分配的对象存在于堆(heap)中而非栈(stack)或者静态区(statically)中。所谓栈,即程序的活动记录(activation record)或者栈帧(stack frame);静态区则是指在编译期或者链接期就可以确定范围的存储区域。堆分配是十分重要的功能,它允许开发者:

在运行时动态地确定新创建对象的大小(从而避免程序在运行时遭遇硬编码数组长度不足产生的失败)。
定义和使用具有递归特征的数据结构,例如链表(list)、树(tree)和映射(map)。
向父过程返回新创建的对象,例如工厂方法。
将一个函数作为另一个函数的返回值,例如函数式语言中的闭包(closure)或者悬挂(suspension)。

在不支持自动化动态内存管理的语言中,众多研究者已经付出了相当大的努力来解决这一难题,其方法主要是管理对象的所有权(ownership)[Belotsky,2003; Cline, Lomo,1995]。Belotsky[2003]等人针对C++提出了几个可行策略:

第一,开发者在任何情况下都应当避免堆分配,例如可以将对象分配在栈上,当创建对象的函数返回之后,栈的弹出(pop)操作会自动将对象释放。
第二,在传递参数与返回值时,应尽量传值而非引用。尽管这些方法避免了分配、释放错误,但其不仅会造成内存方面的压力,而且失去了对象共享的能力。

另外,开发者也可以在一些特殊场景下使用自定义内存分配器,例如对象池(pool of object),在程序的一个阶段完成之后,池中的对象将作为一个整体全部释放。

垃圾算法之间的比较

安全性

垃圾回收器首先要考虑的因素是安全性(safety),即在任何时候都不能回收存活对象。但安全性是需要付出一定代价的,特别是在并发回收器中。

吞吐量

对程序的最终用户而言,程序当然是运行得越快越好,但这是由几方面因素决定的。其中的一方面便是花费在垃圾回收上的时间应当越少越好,文献中通常用标记/构造率(mark/cons ratio)衡量这一指标。这一概念是在早期的Lisp语言中最先提出的,它表示回收器(对存活对象进行标记)与赋值器(mutator)(创建或者构造新的链表单元)活跃度的比值。然而在大多数设计良好的架构中,赋值器会比回收器占用更多的CPU时间,因此在适当牺牲回收器效率的基础上提升赋值器的吞吐量,并进一步提升整个程序(赋值器+回收器)的执行速度,一般来说是值得的。例如,使用标记一清扫回收的系统偶尔会执行存活对象整理以减少内存碎片,虽然这一操作开销较大,但它可以提升赋值器的分配性能。

完整性与及时性

理想情况下,垃圾回收过程应当是完整的,即堆中的所有垃圾最终都应当得到回收,但这通常是不现实的,甚至是不可取的,例如纯粹的引用计数回收器便无法回收环状引用垃圾(自引用结构)。从性能方面考虑,在一次回收过程(collection cycle)中只处理堆中部分对象或许更加合理,例如分代回收器会依照堆中对象的年龄将其划分为两代或者更多代,并把回收的主要精力集中在年轻代,这样不仅可以提高回收效率,而且可以减少单次回收的平均停顿时间(pause time)。

在并发垃圾回收器中,赋值器与回收器同时工作,其目的在于避免或者尽量减少用户程序的停顿。此类回收器会遇到浮动垃圾(floating garbage)问题,即如果某个对象在回收过程启动之后才变成垃圾,那么该对象只能在下一个回收周期内得到回收。因此在并发回收器中,衡量完整性更好的方法是统计所有垃圾的最终回收情况,而不是单个回收周期的回收情况。不同的回收算法在回收及时性(promptness)方面存在较大差异,进而需要在时间和空间上进行权衡。

停顿时间

许多回收器在进行垃圾回收时需要中断赋值器线程,因此会导致在程序执行过程中出现停顿。回收器应当尽量减少对程序主要执行过程的影响,因此要求停顿时间越短越好,这点对于交互式程序或者事务处理服务器(超时将引发事务的重试,进而导致事务的积压)尤为重要。但正如我们在后面章节中将要看到的,限制停顿时间会带来一些副作用。例如,分代式回收器通过频繁且快速地回收较小的、较为年轻的对象来缩短停顿时间,而对较大的、较为年老对象的回收则只是偶尔进行。显然,在对分代回收器进行调优时,需要平衡不同分代的大小,进而才能平衡不同分代之间的停顿时间与回收频率。但由于分代回收器必须记录些分代间指针的来源,因此赋值器的指针写操作会存在少量的额外开销。

并行回收器(parallel collector)虽然也需要停顿整个程序,但它可以通过多线程回收的策略缩短停顿时间。为进一步减少停顿时间,并发回收器与增量回收器(incremental collector)偶尔会将部分回收工作与赋值器动作交替进行或者同时进行,但这一过程需要确保赋值器与回收器之间的同步,因而增大了赋值器的额外开销。回收机制的选择会影响程序在空间和时间两个方面的开销,也会影响垃圾回收周期的结束。赋值器在时间方面的额外开销取决于需要记录的赋值器操作类型(读或者写)及其如何记录。回收器在空间方面的开销以及回收周期的结束取决于系统可以容忍的浮动垃圾数量。多线程赋值器与回收器会增大设计复杂度。不论如何,缩短停顿时间的措施通常会增大整体处理时间(即降低整体处理速度)。

仅对最大或者平均停顿时间进行度量是不够的,必须要同时考虑赋值器的性能,因此停顿时间的分布也值得关注。

空间开销

内存管理的目的是安全且高效地使用内存空间。不论是显式内存管理还是自动内存管理,不同的管理策略均会产生不同程度的空间开销(space overhead)。某些垃圾回收器需要在每个对象内部占用一定的空间(例如保存引用计数),还有一些回收器会复用对象现有布局上已经存在的域(例如将标记位放在对象头部的某个字中,或者将转发指针(forwarding pointer)记录在用户数据上)。回收器也可能会引入堆级别的空间开销,例如复制式回收器需要将堆分为两个半区,任何时候赋值器只能使用一个半区,另一个半区会被回收器保留,并在回收过程中将存活对象复制到其中。回收器也可能需要一些辅助的数据结构,例如追踪式回收器需要通过标记栈来引导堆中指针图表的遍历,回收器在标记对象时也可以使用额外的位图(bitmap)而非对象中的域;对于并发回收器或者其他需要将堆划分为数个独立区域的回收器,其需要额外的记忆集(remembered set)来保存赋值器所修改的指针值或者跨区域指针的位置。

针对特定语言的优化

垃圾回收算法可以根据它们所服务的不同语言范式来归类。在函数式语言中,内存管理有着很大的优化空间。某些语言(例如ML)将可变数据与不可变数据进行区分,纯函数式语言(例如Haskell)则更为极端,它不允许用户改变任何数据,即程序是透明引用(referentially transparent)的。然而,在函数式语言内部,数据结构的更新一般不超过一次,即从待计算值(thunk)到一个弱头部范式(weak head normal form,WHNF),分代垃圾回收器可以据此尽快提升已经完成计算的数据结构。研究者们还提出了基于引用计数来处理环状数据结构的完整机制。声明式语言(declarative language)或许还可以使用其他策略来提升堆空间管理的效率,即如果某一对象创建于一个“选择点”(choice point)之后,那么当程序再次回到该选择点时,该对象将不可达,如果对象在堆中的布局是按照其分配时间排布的,那么某个选择点之后分配的内存可以在一个固定的时间内全部回收。不同种类的语言可能对回收器具有不同的要求,最显著的差异是语言中指针功能的不同,以及回收器调用对象终结的需求不同。

所谓透明引用,即以相同的参数调用同一个函数两次,所得到的结果总是相同的,也可理解为函数没有副作用。
thunk和WHNF均为函数式语言中的与懒情计算相关的概念。

可扩展性与可移植性

可扩展性(scalability)与可移植性(portability)是我们定义的最后两个指标。随着PC,甚至笔记本计算机中(且不说大型服务器)多核硬件的普及,借助硬件的并行优势来提升垃圾回收的性能将变得越来越重要。我们期待并行硬件在规模上(内核与套接字数量上)能有进一步发展,也希望异构处理器(heterogeneous processer)越来越普遍。在服务器方面,堆的大小可以达到数十甚至数百吉字节,事务型负载也越来越多,这些都给垃圾回收带来更多的要求。很多垃圾回收算法需要操作系统或者硬件的支持(例如需要依赖页保护机制,需要对虚拟内存空间进行二次映射,或者要求处理器能够提供特定的原子操作),但这些技术并不需要很强的可移植性。

性能上的劣势

与显式内存管理相比,自动内存管理是否存在性能上的劣势?我们将通过对这一问题的分析,来对两者的优劣进行总结。一般来说,自动内存管理的运行开销很大程度上取决于程序的行为,甚至硬件条件,因而很难对其进行简单评估。一个长期以来的观点是,垃圾回收通常会在总内存吞吐量以及垃圾回收停顿时间方面引人一些不可接受的开销,从而导致应用程序的执行速度慢于显式内存管理策略。自动内存管理确实会牺牲程序的部分性能,但是远不如想象中那样严重。诸如ma1loc和free等显式内存操作也会带来一些显著开销。Herts, Feng, Herger[2005测量了多种Java基准测试程序和回收算法花费在垃圾回收上的真正开销。他们构建了一个Java虚拟机并用其精确地观察到对象何时不可达,同时使用可达追踪的方法驱动模拟器来测量回收周期与高速缓存不命中(cache miss)的情况。他们将许多不同种类的垃圾回收器配置与各种不同的ma1lo/free实现进行比较,比较的方法是:如果追踪发现某一对象变成垃圾,则调用free将其释放。 Herts等人发现,尽管用这两种方式的测量结果差异较大,但是如果堆足够大(达到所需最小空间的5倍),那么垃圾回收器的执行时间性能将可以与显式分配相匹敌,但对于一般大小的堆,垃圾回收的开销会平均增大17%。

实验方法

内存管理涉及时间和空间两方面的权衡。大多数环境下,降低回收停顿时间的一种方法是增大堆的空间(增大到一定程度后将达到最优,但如果再增大,则由于局部性原理,执行时间将会变长)。

术语和符号

首先需要说明的是存储的单位。我们遵循一个字节包含八个位这一惯例。我们简单地使用KB(kilobyte)、MB(megabyte)、GB(gigabyte)、TB(terabyte)来描述对应的2的整数次幂内存单元(分别是20、20、20、20),而不使用SI数字前缀的标准定义。

赋值器与回收器

对于使用垃圾回收的程序, Dijkstra等[1976、1978]将其执行过程划分为两个半独立的部分:

赋值器执行应用代码。这一过程会分配新的对象,并且修改对象之间的引用关系,进而改变堆中对象图的拓扑结构,引用域可能是堆中对象,也可能是根,例如静态变量、线程栈等。随着引用关系的不断变更,部分对象会失去与根的联系,即从根出发沿着对象图的任何一条边进行遍历都无法到达该对象。
回收器(collector)执行垃圾回收代码,即找到不可达对象并将其回收。

一个程序可能拥有多个赋值器线程,但是它们共用同一个堆。相应的,也可能存在多个回收器线程。

分配器

分配器(allocator)与回收器在功能上是正交关系。分配器支持两种操作:分配(allocate)和释放(free)。分配是为某一对象保留底层的内存存储,释放是将内存归还给分配器以便复用。分配存储空间的大小是由一个可选参数来控制的,如果我们在伪代码中忽略这一参数,意味着分配器将返回一个固定大小的对象,或者对象大小对于算法的理解并非必要。分配操作也可能支持更多参数,例如将数组的分配与单个对象的分配进行区分,或者将指针数组的分配和不包含指针的数组进行区分,或者包含其他一些必要信息以便初始化对象头部。

标记-清扫回收

标记一清扫算法是一种间接回收(indirect collection)算法,它并非直接检测垃圾本身而是先确定所有存活对象,然后反过来判定其他对象都是垃圾。需要注意的是,该算法的每次调用都需要重新计算存活对象集合,但并非所有的垃圾回收算法都需要如此。

三色抽象

三色抽象(tricolour abstraction)[Dijkstra等,1976,1978]可以简洁地描述回收过程中对象状态的变化(是否已被标记、是否在工作列表中等)。三色抽象是描述追踪式回收器的种十分有用的方法,利用它可以推演回收器的正确性,这正是回收器必须保证的。在三色抽象中,回收器将对象图划分为黑色对象(确定存活)和白色对象(可能死亡)。任意对象在初始状态下均为白色,当回收器初次扫描到某一对象时将其着为灰色,当完成该对象的扫描并找到其所有子节点之后,回收器会将其着为黑色。从概念上讲,黑色意味着已经被回收器处理过,灰色意味着已经被回收器遍历但尚未完成处理(或者需要再次进行处理)。三色抽象也可以推广到对象的域中:灰色表示正在处理的域,黑色表示已经处理过的域。如果把赋值器也当作一个对象,则三色抽象也可用于推演赋值器根集合的状态变化[Pirinen,1998]灰色赋值器表示回收器尚未完成对其根集合的扫描,黑色赋值器表示回收器已经完成对其根集合的扫描(并且不需要再次扫描)。一次堆遍历过程可以形象地看作是回收器以灰色对象作为“波面”(wavefront),将黑色对象和白色对象分离,不断向前推进波面,直到所有可达对象都变成黑色的过程。

上述算法中存在一个重要的不变式:在标记过程完成后,对象图中将不可能存在从黑色对象指向白色对象的引用,因此在标记过程中,所有白色可达对象都只能是从灰色对象可达。如果这一不变式被打破,那么回收器将不会进一步处理黑色对象,从而可能导致某个黑色对象的后代可达但未被标记(进而被错误地释放)。

改进的标记-清扫算法

程序的性能通常与其高速缓存的相关行为有很大关系。从内存中加载一个值可能要花费上百个时钟周期,但从L1高速缓存(L1 cache)中加载可能只需要花费三到四个时钟周期。高速缓存之所以能够提升程序的性能,主要是因为程序在运行时表现出了良好的时间局部性」(temporal locality),即一旦程序访问了某个内存地址,则很可能在不久之后再次访问该地址,因此值得将它的值缓存。程序也可能表现出良好的空间局部性(space locality),即一旦程序访问了某个内存地址,则很有可能在不久之后访问该地址附近的数据。现代硬件可以从两个方面利用程序的局部性特征:一方面,高速缓存与更低级别内存之间不会进行单个字节的数据传输,而是以一个固定的字节数为最小传输单元(即高速缓存行或者高速缓存块的大小),通常是32~128字节;另一方面,处理器可能会使用硬件预取(prefetch)技术,例如Intel Core微处理器架构可以探测到有规律的步进内存访问操作,进而提前读取数据流。开发者也可以利用显式预取指令引导预取过程。

位图标记

回收器可以将对象的标记位保存在其头部的某个字中,除此之外也可以使用一个独立的位图来维护标记位,即:位图中的每个位关联堆中每个可能分配对象的地址。位图所需的空间取决于虚拟机的字节对齐要求。位图可以只有一个,也可以存在多个,例如在块结构的堆中,回收器可以为每个内存块维护独立的位图,这一方式可以避免由于堆不连续导致的内存浪费。回收器可以将每个内存块的位图置于其自身内部,但如果所有内存块中位图的相对位置全部相同,则可能导致性能的下降,因为不同内存块的位图之间可能会争用相同的组相关高速缓存(set- associative cache)。对位图的访问同时也意味着对位图所在页的访问(即可能导致缺页异常——译者注),因此基于换页和高速缓存相关性的考虑,在访问位图时花费更多的指令以保持程序的局部性通常来说是值得的。为避免高速缓存的相关问题,可以将内存块中位图的位置增加一个简单偏移量,例如内存块地址的简单哈希值。还可以将位图存放在个额外的区域[Boehm and Weiser,1988年]中,并以其所对应内存块的哈希值等作为索引,这样既避免了换页问题,也避免了高速缓存冲突。

位图标记通常仅适用于单线程环境,因为多线程同时修改位图可能存在较大的写冲突风险。设置对象头部中的标记位通常是安全的,因为该操作是幂等的,即最多只会将标记位设置多次。相对于位图,实践中更常用的是字节图(byte-map),虽然它占用的空间是前者的8倍,但却解决了写冲突问题。另外还可以使用同步操作来设置位图中的位。在实际应用中,如果将标记位保存在对象头部通常会带来额外的复杂度,因为头部通常会存放一些赋值器共享数据,例如锁或者哈希值,那么当标记线程与赋值器线程并发执行时可能会产生冲突。因此,为了确保安全,标记位通常会占用头部中一个额外的字,以便与赋值器共享数据区分,当然也可以使用原子操作来设置头部中的标记位。

相对于将标记位放置在对象头部这一策略,位图可以使得标记位更加密集;对于使用位图的标记一清扫回收器,标记过程只需读取存活对象的指针域而不会修改任何对象;对于不包含引用的对象,回收器只需要读取其类型信息描述域;清扫器不会对存活对象进行任何读写操作,它只会在释放垃圾对象的过程中覆盖其某些域(例如将它们链接到空闲链表上)。因此,位图标记不仅可以减少内存中需要修改的字节数,而且减少了对高速缓存行的写入,进而减少需要写回内存的数据量。

位图标记最初应用在保守式回收器(conservative collector)中。保守式回收器的设计初衷是为C和C++等“不合作”的语言提供自动内存管理功能[Boehm and Weiser,1988]型精确(type-accurate)系统可以精确地识别每一个包含指针的槽,不论其位于对象中,是位于线程栈或者其他根集合中,而保守式回收器则无法得到编译器和运行时系统的支持因而其在识别指针时必须采用保守的判定方式,即:如果槽中某个值看起来像是指针引用,那么就必须假定它是一个指针。保守式回收器可能错误地将一个槽当作指针,这带来了两个安全上的要求:第一,回收器不能修改任何赋值器可能访问到的内存地址的值(包括对象和根集合)。这一要求导致保守式回收器不能使F任何可能移动对象的算法,因为对象被移动之后需要更新指向该对象的所有引用。这同时导致在头域中保存标记位的方案不可行,因为错误的指针会指向一个实际并不存在的象”,因此设置或者清理标记位可能会破坏用户数据。第二,应当尽可能减少赋值器破坏回收器数据的可能性。与将标记位等回收器元数据存放在一个单独区域的方案相比,为每个对象增加一个回收器专用头部数据会存在更高的风险。

使用位图标记的另一个重要目的是减少回收过程中的换页次数[Boehm,2000在现代系统中,任何由回收器导致的换页行为通常都是不可接受的,因此位图标记是否可以提升高速缓存性能便成为一个值得关注的问题。许多证据表明,对象往往成簇诞生并成批死亡[Hayes,1991; Jones, Ryder,2008],而许多分配器往往也会将这些对象分配在相邻的空间。使用位图来引导清扫可以带来两个好处:第一,在位图/字节图中,一个字内部的每个位/字节全部都被设置/清空的情况会经常出现,因此回收器可以批量读取/清空一批对象的标记位;第二,通过位图标记可以更简单地判定某一内存块中的所有对象是否都是垃圾,进而可能一次性回收整个内存块。

许多内存管理器都使用块结构堆(如Boehm and Weiser[1988])。最直接的位图标记实现策略可能是在每个内存块的前端保留一块内存以用作位图。但正如我们前面所提到的,这策略可能会导致不必要的高速缓存冲突或者换页,因此回收器通常将位图与用户数据块分开并单独存放。

Garner等[2007]提出了一种混合标记策略,即将分区适应分配器(segregated fitsallocator)所管理的每个数据块与字节图中的一个字节相关联,同时依然保留对象头部的标记位。当且仅当内存块中至少存在一个存活对象时,该内存块所对应的标记字节才会被设置。清扫器可以根据字节图快速地判定某一内存块是否完全为空(即不包含存活对象),进而可以将其整体回收。这一策略有两个优点:第一,在并发情况下,无需使用同步操作来设置字节图中的标记字节以及对象头部的标记位;第二,写操作没有数据依赖(这可能导致高速缓存延迟),且对字节图中标记字节的写操作也是无条件的。

标记过程中的高速缓存不命中问题

Bohm[2000]发现标记过程的开销决定着回收时间:在 Intel PentiumⅢ系统中,预取对象第一个指针域的开销通常会占到标记该对象总开销的三分之一。为此 Boehm提出一种灰色预取( prefetching on gray)技术,即当对象为灰色时,预取其第一个高速缓存行中的数据,如果被扫描的对象很大,则预取适当数量的高速缓存行。然而,这种技术依赖于预取时间,如果过早地进行高速缓存行预取,则数据很可能在得到使用之前就被换出,而过晚地预取则会导致高速缓存不命中。

需要考虑的问题

空间利用率

将标记位放在对象头部基本不会产生额外的空间开销,而如果使用位图来保存标记位,则额外空间开销的大小取决于对象的字节对齐要求,但其总大小不会超过堆的字节对齐要求的倒数(即堆空间的1/64或1/32,具体的值取决于堆的组织架构)。

引用计数

环状引用计数

对于环状数据结构而言,其内部对象的引用计数至少为1,因此仅靠引用计数本身无法回收环状垃圾。不论是在应用程序还是在运行时系统中,环状数据结构都十分普遍,如双向链表或者环状缓冲区。对象一关系映射(object-relations mapping)系统可能要求数据库和其中的表互相引用对方的一些信息。真实世界中的某些结构天然就是环状的,例如地理信息系统中的道路。懒惰函数式语言(lazy functional language)通常使用环来表示递归[urner 1979,Y组合子(Combinator)]。研究者们提出了多种解决环状引用计数问题的策略,我们介绍其中的几种。

最简单的策略是在引用计数之外偶尔使用追踪式回收作为补充。该方法假定大多数对象不会被环状数据结构所引用,因此可以通过引用计数方法实现快速回收,而追踪式回收则负责处理剩余的环状数据结构。这一方案简单地减少了追踪式回收的发起频率。在语言层面上, Friedman和wise[1979]发现,纯函数式语言中只有递归定义才会产生环,因此只要遵从一定的规则便可对这种情况下的环状引用计数进行特殊处理。在 Bobrow1980]的方法中,开发者可以把一组对象作为整体进行引用计数操作,当整体引用计数为零时便可将其集体回收。

许多学者建议将导致闭环出现的指针与其他指针进行区分[Friedman and Wise,1979;Brownbridge,1985; Salkeld,1987; Repels等,1988; Axford,19901。他们将普通引用称为强引用(strong reference),将导致闭环出现的引用称为弱引用(weak reference)。如果不允许强引用组成环,则强引用图可以使用标准引用计数算法处理。Brownbridge的算法得到了广泛应用,简而言之,每个对象需要包含一个强引用计数以及一个弱引用计数,在进行写操作时,写屏障会检测指针以及目标对象的强弱,并将所有可能产生环的引用设置为弱引用。为维护“所有可达对象均为强可达,且强引用不产生环”这一不变式,赋值器在删除引用时可能需要改变指针的强弱属性。但是,这一算法并不安全,且可能导致对象提前被回收,具体可以参见Salkeld的引用计数示例[Jones,1996,6.5节]。Salkeld[1987]对该算法进行修正并提升了它的安全性,但代价是在某些情况下算法将无法结束。Repels等[1988]提出了一种非常复杂的解决方案,但该算法在空间以及性能方面的开销却更加明显:与普通的引用计数相比,其所需的空间开销翻倍,在大多数情况下,其性能开销是标准引用计数的两倍,在极端情况下,甚至会呈现指数级增长。

在所有能够处理环状数据结构的引用计数算法中,得到了最广泛认可的是试验删除(trial deletion)算法。该算法无须使用后备的追踪式回收器来进行整个存活对象图的扫描,相反,它将注意力集中在可能会因删除引用而产生环状垃圾的局部对象图上。在引用计数算法中:

在环状垃圾指针结构内部,所有对象的引用计数均由其内部对象之间的指针产生。
只有在删除某一对象的某个引用后该对象的引用计数仍大于零时,才有可能出现环状垃圾。

部分追踪(partial tracing)算法充分利用上述两个结论,该算法从一个可能是垃圾的对象开始进行子图追踪。对于遍历到的每个引用,算法将对其目标对象进行试验删除,即临时性地减少目标对象的引用计数,从而移除由内部指针产生的引用计数。追踪完成后,如果某个对象的引用计数仍然不是零,则必然是因为子图之外的其他对象引用了该对象,进而可以判定该对象及其传递闭包都不是垃圾。

Recycler算法[Bacon等,2001; Bacon and Rajan,2001;Paz等,2007]支持环状引用计数的并发回收。环状数据结构的回收分为3个阶段:

首先,回收器从某个可能是环状垃圾成员的对象出发进行子图追踪,同时减少由内部指针产生的引用计数。算法将遍历到的对象着为灰色。
其次,对子图中的所有对象进行检测,如果某一对象的引用计数不是零,则该对象必然被子图外的其他对象引用。此时需要对第一阶段的试验删除操作进行修正,算法将存活的灰色对象重新着为黑色,同时将其他灰色对象着为白色。
最后,子图中所有依然为白色的对象必然是垃圾,算法可以将其回收。

内存分配

对于首次适应或循环首次适应分配而言,将空闲内存单元依照地址进行排序的另一种有效策略是位图适应分配(bitmapped- fits allocation)。该算法使用额外的位图来记录堆中每个可分配内存颗粒的状态,因此在进行内存分配时,分配器可以基于位图而非堆本身进行搜索。借助一张预先计算好的映射表,分配器仅需要对位图中一个字节进行计算,便可得知其所对应的8个连续内存颗粒所能组成的最长连续可用空间。也可以使用额外的长度信息记录较大的空闲内存单元或者已分配内存单元,从而快速将其跳过以提升分配性能。位图适应分配具有如下一些优点:

位图本身与对象相互隔离,因此不容易遭到破坏。这一特性不仅对于诸如C和C++等安全性稍低的语言十分重要,而且对于安全性更高的语言也十分有用,因为这可以提升回收器的可靠性以及可调试性。
引入位图之后,无论是对于空闲内存单元还是已分配内存单元,回收器都不需要占据其中的任何空间来记录回收相关信息,从而最大限度地降低了对内存单元大小的要求。如果以一个32位的字作为最小内存分配单元,该策略会引入大约3%的空间开销,但其所带来收益却远大于这一开销。不过,基于其他一些方面的考虑,对象可能依然需要一个头部,因而这一优点并非始终能够得到体现。
相对于堆中的内存单元,位图更加紧凑,因此基于位图进行扫描可以提升高速缓存命中率,从而提升分配器的局部性。

分区适应分配

空间大小分级的填充

伙伴系统(buddy system)其空间大小分级均为2的整数次幂[Knowlton,1965; Peterson and Norman,1977]。我们可以将一个大小为2^(i+1)的空闲内存单元分裂为两个大小为2^i的空闲内存单元,同时也可以将两个相邻的大小为2^i的空闲内存单元合并成大小为2^(i+1)的一个,但进行合并的前提是两个相邻空闲内存单元原本就是由同一个较大的空闲内存单元分裂得到的。在该算法中,大小为2^i的空闲内存单元两两成对,因而称之为伙伴。由于伙伴系统的内部碎片通常较为严重(对于任意的内存分配需求,其平均空间浪费率会达到25%),因此该算法基本已经成为历史,在实践中较少使用。

斐波那契伙伴系统(Fibonacci buddy system)[Hirschberg,1973; Burton,1976; Peterson and
Norman,1977是伙伴系统的一个变种,其空间大小分级符合斐波那契序列,即s_i+2 = s_i+1 + s_i,同时需要选定合适的s0和s1。与传统的伙伴系统相比,该算法相邻空闲内存单元的大小比值更小,因而在一定程度上缓解了内部碎片问题。但该算法的问题在于,在回收完成后将相邻空闲内存单元合并的操作会更加复杂,因为回收器需要判定某一空闲内存单元究竟应当与相邻两个空闲内存单元中的哪一个进行合并。

其它需要考虑的问题

字节对齐

将对象按照特定的边界要求进行对齐,一方面是底层硬件或者机器指令集的要求,另方面这样做有助于提升各层次存储器的性能(包括高速缓存、转译后备缓冲区、内存页以Java语言的 double数组为例,某些机器可能要求double这一双字浮点数必须以双字为边
界进行对齐,即其地址必须是8的整数倍(地址的后三位为零)。一种简单但稍显浪费的解决方案是将双字作为内存分配的颗粒,即所有已分配或未分配内存单元的大小均为8的整数倍,且均按照8字节边界对齐。但即便如此,当分配一个doub1e类型的数组时,分配器仍需要进行一些额外工作。假设Java语言中纯对象(即非数组对象)头部都必须保留两个字,一个指向对象的类型信息(用于虚函数调用、类型判定等),另一个用于记录对象的哈希值以及同步操作所需的锁(这也是一种典型的设计方式)。数组对象则需要第三个字来记录其中元素的个数。如果将这三个头部字保存在已分配内存单元的起始位置,则数组元素就不得不以奇数字为单位进行对齐。如果使用双字作为内存颗粒,则可以简单地用四个字(即两个双字)来保存这三个头部字,然后浪费掉一个。

但如果内存颗粒是一个字,我们则希望尽量减少上述的内存浪费。此时,如果某个空闲内存单元按照奇数字对齐(即其地址模8余4),则我们可以简单地将三个头部字放在内存单字对齐,则我们必须浪费一个字以满足对齐要求。这一方案增加了分配过程的复杂度,因为某一空闲内存单元是否满足分配需求不仅取决于所需空间的大小,还取决于字节对齐要求。

字：16个位为一个字，它代表计算机处理指令或数据的二进制数位数，是计算机进行数据存储和数据处理的运算的单位。通常称16位是一个字，而32位呢，则是一个双字，64位是两个双字。

空间大小限制

某些回收器要求对象(内存单元)的大小必须大于某一下界。例如,基本的整理式回收要求对象内部至少可以容纳一个指针,还有一些回收器可能需要用两个字来保存锁或状态以及转发指针,这就意味着即使开发者仅需要分配一个字,分配器也必须多分配两个字。如果开发者需要分配不包含任何数据、仅用作唯一标识的对象,原则上编译器无需分配任何空间,但在实际情况下这通常不可行:对象必须要有唯一的地址,因此对象的大小至少应为一个字节。

边界标签

为了确保在释放内存时可以将相邻空闲内存单元合并,许多内存分配系统为每个内存单元增加了额外的头部或者边界标签,它们通常不属于可用内存的范畴[Knuth,1973]。边界标签保存了内存单元的大小及其状态(即空闲或已分配),还可以在其中记录上一个内存单元的大小,从而可以快速读取上一个内存单元的状态并判断其是否为空。当内存单元空闲时,边界标签也可用于保存构建空闲链表的指针。基于这些原因,边界标签可能达到两个字或者更大,但如果使用一些额外的方法,并允许在分配和释放的过程中引入一定的额外开销,则仍有可能将边界标签压缩到一个字。

如果使用额外的位图来标记堆中每个内存颗粒的状态,则不仅无需使用边界标签,而且可以增加程序的鲁棒性。这一方法是否会减少空间开销,取决于对象的平均大小以及内存颗粒的大小。

我们进一步注意到,垃圾回收通常会一次性释放大量对象,因此某些特定的算法可能不再需要边界标签,或者其边界标签中需要包含的信息较少。另外,托管语言中对象的大小通常可以通过其类型得出,因而无需使用额外的边界标签来单独记录相关信息。

局部性

事实证明,同一时刻分配的对象通常也会在同一时刻成为垃圾,因此非移动式回收器所面临的内存碎片问题比人们预想的要小[Hayes,1991; Dimpsey等,2000; Blackburn and McKinley,2008],这同时也说明,将连续两次分配的对象连续排列或者尽可能靠近排列的启发式方法是有价值的。

并发系统中的内存分配

在多线程环境下,分配过程的许多操作都需要原子化以确保分配数据结构的完整性,这些操作都必须使用原子操作或者锁,但这样一来,内存分配就可能成为性能瓶颈。最基本的解决方案是为每个线程开辟独立的内存分配空间,如果某个线程的可分配空间耗尽,则从全局内存池中为其分配一个新的空闲块,此时只有与全局内存池的交互才需要原子化。不同线程的内存分配频度可能不同,因此如果在为线程分配内存块时使用自适应算法(即:为分配速度较慢的线程分配较小的内存块,而为分配速度较快的线程分配较大的内存块),则程序的时间和空间性能均可获得提升。Dimpsey等[20001声称,在多处理器Java系统中,为每个线程配备一个合适的本地分配缓冲区(local allocation buffer,LAB)可以大幅提升性能。他们进一步指出,由于几乎所有的小对象都是从本地分配缓冲区分配的,因而我们有理由对全局(基于空闲链表的)分配器进行调整,以使其能够更加高效地分配用于线程本地分配缓冲区的内存块。

Garthwaite等[2005]讨论了如何对本地分配缓冲区的大小进行自适应调整,他们同时发现,将本地分配缓冲区与处理器而非线程相关联效果更佳。该算法通过如下方式对本地分配缓冲区的大小进行调整:线程初次申请本地分配缓冲区时将获得24个字的内存块,之后每次新申请的内存块均为上一次的1.5倍,同时每经历一次垃圾回收过程,回收器都会将线程的本地分配缓冲区的大小折半。该算法同时也会根据不同线程的分配次数调整年轻代的空间大小。每处理器(per-processor)本地分配缓冲区的实现依赖于多处理器的可重启临界区(restartable critical section),Garthwaite等人对此做了介绍。其基本原理是,线程可以判断自身是否被抢占(preempt)或者被重新调度(reschedule),然后可以据此判断自身是否被切换到其他处理器上运行。当线程抢占发生时,处理器会对某个本地寄存器进行修改,该操作会为抢占完成后的写入操作设置一个陷阱,而陷阱处理函数则会重启被中断的分配过程。尽管每处理器本地分配缓冲区需要更多的指令支持,但与每线程本地分配缓冲区相比,其分配时延相同,且不需要复杂的缓冲区调整机制。 Garthwaite同时发现,当线程数量较少时(特别是当线程数量小于处理器数量时),每线程(per-thread)本地分配缓冲区的性能较好,而在线程数量较多的情况下,每处理器本地分配缓冲区的表现更佳,因此他们将系统设计成可在两种方案之间进行动态切换。

本地分配缓冲区通常使用顺序分配策略。每个线程(或处理器)也可以独立维护自身对应的分区适应空闲链表,同时使用增量清扫策略。线程在内存分配过程中会执行增量清扫,并将清扫所得的空闲内存单元添加到自身空闲链表中,但Berger等[2000]指出,如果将该算法用于显式内存管理会存在一些问题。例如,在某一使用生产者一消费者模型的程序中消息对象通常由生产者创建并由消费者释放,因此两个线程之间将会产生单方向的内存转移。在垃圾回收环境下通常不会存在这一问题,因为回收器可以将空闲内存释放到全局内存池中。如果使用增量清扫,空闲内存单元将被执行清扫的线程所获取,从而自然地将回收所得的内存返还给分配最频繁的线程。

需要考虑的问题

使用额外的位图表来标记内存颗粒的状态(空闲/已分配)以及内存单元/对象的起始地址,不仅能提升程序的鲁棒性,而且可以简化对象头部的设计。该策略同时可以加速回收器的操作,并可以在存储器层次结构方面提升回收器的性能。基于位图的分配策略空间开销不大,但其分配过程通常会存在额外的时间开销。

分代间指针

分代间指针的创建有3种方式:一是在对象创建时写入,二是在赋值器更新指针槽时写入,三是在将对象移动到其他分代时产生。回收器必须要对分代间指针进行记录,只有这样才能确保在对某一分代单独进行回收时根的完整性。

记忆集

因此,每个分代的记忆集均只需记录可能指向该分代内部对象的回收相关指针来源。不同的记忆集实现方式在来源地址的记录方面所能达到的精度也各不相同。精度并非越髙越好,较高的精度通常会增大赋值器的额外开销、记忆集空间开销以及回收器处理记忆集的时间开销。

带式回收框架

回收策略的基本指导思想大体上可以总结如下:

“大多数对象都在年轻时死亡”,即弱分代假说。
分代回收器会避免对年老对象进行频繁回收。
增量回收可以改善回收停顿时间。在分代垃圾回收器中,新生代的空间通常较小;其他回收技术通常也会限制待回收空间的大小,例如成熟对象空间回收器(mature object space collector)(也称为火车回收器)。
在较小的诞生空间中使用顺序分配可以提升数据的局部性。
对象需要足够的时间到达死亡。

启发式方法在分代垃圾回收中的应用

分代垃圾回收器可以较好地处理短命对象,但其对长寿对象的处理能力则略显不足,这一问题主要表现在两个方面:第一,年老代垃圾的回收不够及时,因为没有哪种策略可以确保在年老代出现大量垃圾时尽快将其回收;第二,年老代的所有长寿对象都必须是从年轻代复制而来的,同时为避免过早地提升对象,某些回收器要求年轻代对象在得到提升之前必须在年轻代中经历数次回收。对于长寿对象而言,这些复制操作都相当于是无用功,更好的解决方案是直接将长寿对象预分配到其最终可能到达的分代中。

一些研究者尝试通过分析程序特定代码位置所分配对象的生命周期分布来解决这一问题。这一方案对于虚拟机的开发者来说具有一定的可行性,因为他们可以知道在其具体的虚拟机中哪些数据结构会是永久性的、哪些库或者代码对象永远不会或者至少不太可能被卸载。这些对象的预分配逻辑可以在虚拟机内部实现。

其他分区策略

每种回收器都通过一种不同的方式来解决如下3个问题:

如何最好地利用堆空间
如何避免对去碎片化操作(复制或标记一整理)的依赖
如何降低回收器循环的时间开销

运行时接口

我们将对象的分配以及初始化过程划分为3个阶段,但并非所有的语言或者所有情况下都需要完成所有阶段。

阶段1:分配一块大小合适的、符合字节对齐要求的内存单元,这一工作是由内存管理器的分配子系统完成的。
阶段2:系统级初始化(system initialisation),即在对象被用户程序访问之前,其所有的域都必须初始化到适当的值。例如在面向对象语言中,设定新分配对象的方法分派向量(method dispatch vector)即是该阶段的任务之一。该阶段通常也需要在对象头部设置编程语言或内存管理器所需的头域,对Java对象而言,则包括哈希值以及同步相关信息,而Java数组则需要明确记录其长度。
阶段3:次级初始化(secondary initialisation),即在对象已经“脱离”分配子空间,并且可以潜在被程序的其他部分、线程访问时,进一步设置(或更新)其某些域。

Java:阶段1和阶段2共同完成新对象的方法分派向量、哈希值、同步信息的初始化,同时将所有其他域设置为某一默认值(通常全为零)。数组的长度域也在这两个阶段完成初始化。字节码new所返回的对象便处于这一状态,此时尽管对象满足类型安全要求,但其依然是完全“空白”的对象。阶段3在Java语言中对应的表现形式是对象构造函数或者静态初始化程序中的代码,或者在对象创建完成后将某些域设置为非零值的代码段。final域的初始化也是在阶段3中完成的,因此一旦过早地将新创建的对象暴露给其他线程,同时又要避免其他线程感知到对象域的变化,实现起来将十分复杂。

来自外部代码的引用

句柄不仅可以作为托管堆和非托管世界之间的一道桥梁,而且可以更好地适应移动式回收器,但并非所有的外部访问都可以遵从这一访问协议,特别是操作系统调用。此时回收器就必须避免移动被外部代码所引用的对象。为此,回收器可能需要提供一个钉住接口,并提供钉住(pin)和解钉(unpin)操作,当某一对象被钉住时,回收器将不会移动该对象,同时也意味着该对象可达且不会被回收。

如果我们在分配对象时便知道该对象可能需要钉住,则可以直接将其分配到非移动空间中。文件流IO缓冲区便是以这种方式进行分配的。但程序通常很难事先判断哪个对象未来需要钉住,因此某些语言支持pin和unpin函数以便开发者自主进行任何对象的钉住与解钉操作。

钉住操作在非移动式回收器中不会成为问题,但却会给移动式回收器造成一定不便,针对这一问题存在多种解决方案,每种方案各有优劣。

延迟回收,或者至少对包含被钉住对象的区域延迟回收。该方案实现简单,但却有可能在解钉之前耗尽内存。
如果应用程序需要钉住某一对象,且对象当前位于可移动区域中,则我们可以立即回收该对象所在的区域(以及其他必须同时回收的区域)并将其移动到非移动区域中。该策略适用于钉住操作不频繁的场景,同时也适用于将新生代存活对象提升到非移动式成熟空间的回收器(例如分代回收器)。
对回收器进行扩展以便在回收时不移动被钉住的对象,但这会增加回收器的复杂度并可能引入新的效率问题。

针对代码的回收

许多系统会预先对所有代码进行静态编译,但也有一些程序可以在运行时构建并执行代码,例如垃圾回收技术的鼻祖—Lisp语言。尽管Lisp最初是解释型语言,但其在很早就已经能够编译成本地代码。目前,越来越多的系统已经能够动态加载或者构建代码,并在运行时进行优化。由于系统可以动态加载或者生成代码,所以我们自然会希望当这些代码不再使用时,其所占用的空间能够得到回收。面对这一问题,直接的追踪式或引用计数算法通常无法满足该要求,因为许多从全局变量或者符号表可达的函数代码将永远无法清空。某些语言只能靠开发者显式卸载这些代码实例,但语言本身甚至可能根本不支持这一操作。

另外,还有两个特殊场景值得进一步关注。首先是由一个函数和一组环境变量绑定而成的闭包。我们假设某一简单的闭包是由内嵌在函数f中的函数g,以及函数f的完整环境变量构成的,它们之间可能会共享某一环境对象。Thomas和Jones[1994]描述了一种系统,该系统可以在进行垃圾回收时将闭包的环境变量特化为仅由函数g使用的变量。该策略可以确保某些其他闭包最终不可达并得到回收。

另一种场景出现在基于类的系统中,例如Java。此类系统中的对象实例通常会引用其所属类型的信息。系统通常会将类型信息及其方法所对应的代码保存在非移动的、不会进行垃圾回收的区域,因此回收器便可忽略掉所有对象中指向类型信息的指针。但是如果要回收类型信息,回收器就必须要对所有对象中指向类型信息的指针进行追踪,在正常情况下这一操作可能会显著增大回收开销。回收器可以仅在特殊模式下才对指向类型信息的指针进行追踪。

对于Java而言,运行时类是由其类代码以及类加载器(class loader)同决定的由于系统在加载类时通常会存在一些副作用(例如初始化静态变量),所以类的卸载会变得不透明(即存在副作用—译者注),这是因为该类可能会被同一个类加载器重新加载。唯一可以确保该类不被某个类加载器加载的方法是使类加载器本身也能得到回收。类加载器中包含一个已加载类表(以避免重复加载或者重复初始化等),运行时类也需要引用其类加载器(作为自身标识的一部分)。因此,如果要回收一个类,则必须确保其类加载器、该类加载器所加载的其他类、所有由该类加载器所加载的类的实例都不被现有的线程以及全局变量所引用(此处的全局变量应当是由其他类加载器加载的类的实例)。另外,由于引导类加载器(bootstrap class loader)永远不会被回收,所以其所加载的任何类都无法得到回收。由于Java类卸载是一种特殊的情况,所以某些依赖这一特性的程序或者服务器可能会因此耗尽空间。

读写屏障

卡表

卡表(卡标记)策略将堆在逻辑上划分为固定大小的连续区域,每个区域称之为卡。卡通常较小,介于128~512字节之间。卡表最简单的实现方案是使用字节数组,并以卡的编号作为索引。当某个卡内部发生指针写操作时,写屏障将该卡在卡表中对应的字节设置为脏。卡的索引号可以通过对指针域的地址进行移位获得。卡表的设计初衷在于尽量简化写屏障的实现并提高其性能,从而将其内联到赋值器代码中。另外,与哈希表或者顺序存储缓冲区不同,卡表不存在溢出问题。但这些收益总是要付出一定代价的:回收器的工作负荷会加重,因为回收器必须对脏卡中的域进行逐个扫描,并找出其中已被修改的、可能包含回收相关指针的域,此时回收器的工作量将正比于已标记卡的数量(以及卡的大小),而非产生回收相关指针的写操作的发生次数。

使用卡表的目的在于尽可能减轻赋值器的负担,因而其通常应用在无条件写屏障中,这便意味着卡表必须能够将所有可能被 Write操作修改的地址映射到卡表中的某个槽。如果我们可以确保堆中的某些区域永远不可能写入回收相关指针,同时引入条件检测来过滤掉这些区域的指针写操作,则可以减少卡表的大小。例如,如果将堆中高于某一固定虚拟地址边界的空间用作新生区(回收器在每次回收过程中都处理该区域),则卡表只需要对低于该边界地址的空间创建对应的槽。

最紧凑的卡表实现方式应当是位数组,但多种因素决定了位数组并非最佳实现方案。现代处理器的指令集并不会针对单个位的写入设置单独的指令,因而位操作比原始操作需要更多的指令:读取一个字节、通过逻辑运算设置或清除一个位、写回该字节。更糟糕的是,这些操作序列并不是原子化的,多线程同时更新同一个卡表条目可能会导致某些信息丢失,即使它们所修改的是堆中不同的域或者对象。正因如此,卡表才通常使用字节数组。由于处理器清空内存的指令的执行速度更快,所以通常使用0来表示“脏”标记。在使用字节数组的场景下,在卡表中设置脏标记只需要两条SPARC指令(其他架构所需的指令可能会稍多一些)。

Detlefs等观察发现,绝大多数卡都是干净的,且单个卡中很少会包含超过16个分代间指针。因此可以使用两级卡表来加速回收器查找脏卡的过程,尽管这一策略会付出额外的空间开销。第二级卡占用的空间更小,其中的每个槽对应2ⁿ个粒度更细的卡,因而其能够将干净卡的扫描速度提升n倍。

特定语言相关内容

弱引用

对不同强度指针的支持

每种强度的引用通常会与回收器的特定行为相关联。在支持多种不同强度的弱引用的编程语言中,最知名的当属Java,其提供的引用类型从最强到最弱可以分为以下几种:

强引用(strong reference):普通的引用,具有最高的引用强度。回收器永远不会将强引用置空。
软引用(soft reference):回收器可以根据当前的空间使用率来判定是否需要将软引用置空。如果Jaa回收器将某个指向对象O的软引用置空,它必须在同一时刻自动将所有导致对象O强可达的软引用置空。这一规则可以确保在回收器将这些引用置空之后,对象将不再软可达。
弱引用(weak reference):一旦回收器发现某一(软可达的)弱引用的目标对象变为弱可达,则回收器必须将该引用置空(从而确保其目标对象不再软可达)。与软引用类似旦回收器将某个指向对象O的弱引用置空,则必须同时将所有其他导致该对象软可达的软可达弱引用置空。
终结方法引用(finaliser reference):我们将从终结表到待终结对象的引用称为终结方法引用。终结方法引用只在运行时系统内部出现,它并不会像弱对象一样暴露给开发者。
虚引用(phantom reference):Java中最弱的一种引用类型。虚引用只有与通知机制联合使用才具有一定意义,这是因为虚引用对象不允许程序经由该引用获取目标对象的引用,因此程序唯一可能的操作是将虚引用置空。程序必须显式地将虚引用置空来确保回收器将其目标对象回收。

Java语言中不同强度的引用并没有我们此处描述的这么多,但此处的每种语义却与语言规范所定义的每种弱引用相关联。软引用允许系统对可调整的缓存进行收缩;弱引用可以用于规范化表或者其他场景;虚引用允许开发者控制回收的顺序以及时间。

多强度引用的实现需要在回收过程中增加额外的遍历,但这些操作通常可以很快完成。下面我们以Java的4种强度为例来描述复制式回收器对不同强度引用的处理方式。标记清扫回收器也可以通过类似的方式实现,同时也会更加简单。回收器应当以如下方式执行堆遍历过程：
1)从根开始,仅对强可达对象进行追踪并复制,同时找出所有的软对象、弱对象、虚对象(但不对这些对象进行追踪)。
2)如果必要,则自动将所有软引用置空。如果无需将软引用置空,则需对其进行追踪和复制,并找出所有的软可达对象。对软可达对象进行追踪时可能会发现新的弱可达或虚可达对象。
3)如果弱引用的目标对象已被复制到目标空间,则更新该引用,否则将该引用置空。
4)如果尚未复制的对象中存在需要终结的对象,则将其加入终结队列,然后回到第1步,并以终结队列作为新的根进行追踪。需要注意的是,在第二轮执行过程中将不会再有需要终结的对象产生。
5)如果虚引用的目标对象并未得到复制,则将其加入ReferenceQueue里。然后回收器将从该对象开始完成虚可达对象的追踪与复制。需要注意的是,回收器不会将任何虚引用置空,这一操作必须由开发者显式操作。

使用虚对象控制终结顺序

假设有两个对象,A和B,我们希望它们的终结顺序是先A后B。一种实现策略是创建虚对象A来持有对象A的虚引用。除此之外,A的类型应该是对Java的PhantomReference的扩展,其将持有一个指向对象B的强引用,以避免对象B被提早终结。图12.5演示了这一情况。

一旦对象A’(即对象A的虚引用来源)加入到用户指定的队列,意味着对象A已经从应用程序不可达,并且A对应的终结方法已经运行过,这是因为终结队列可达要比虚可达的强度更高。然后我们将虚对象A指向A的虚引用图12.5按序终结。我们希望在对象A和B置空,再将其指向B的强引用置空,如此一来,对象B的终结方法将在下一轮回收中得到调用最后我们再把虚对象从全局对象表中删除,则虚对象本身也将得到回收。我们很容易将该策略进行推广,进而实现三个或者更多对象的终结顺序控制,所付出的代价是在两两对象之间通过虚对象来施加终结顺序限制。

终结顺序的控制只能通过虚对象完成,弱对象无法胜任。对于图12.5所示的状态,如果我们将虚对象替换为弱对象,则当对象A不可达时,A中的弱引用将被置空,且A’将被添加到用户指定的队列中。此时我们可以将A中指向B的强引用置空,但不幸的是,置空A中弱引用的操作将发生在A的终结方法执行之前(因为弱引用的强度高于终结方法引用——译者注),此时我们将很难知道A的终结方法何时执行完毕,因此对象B的终结方法可能会先得到执行。故意将虚引用的强度设计得比终结方法引用更低,目的正在于确保只有当对象的终结方法执行完毕之后,其虚引用来源才会被加入到用户指定的队列。

弱指针置空时的通知

在弱引用机制之上,某些应用程序可能需要在特定的弱引用被清空时得到通知(虚引用可以通知应用程序对象已被终结,而弱引用则可以通知应用程序对象可能将要终结),然后再执行某些适当的动作。因此,弱引用机制通常也会支持通知,其实现策略一般是将弱对象添加到开发者指定的队列中。例如,Java的ReferenceQueue内建类便是以此为目的设计的,应用程序既可以对其进行轮询,也可使用阻塞式的操作来获取元素(或者附加额外的超时时间)。应用程序也可以检测某个给定的弱对象是否已经加入到某个队列中(Java只允许弱对象最多被加入到一个队列中)。回收器在对弱指针的多次遍历过程中可以很轻松地实现弱对象的人队。许多语言都增加了类似的通知机制。

并发算法预备知识

硬件

处理器与线程

处理器(processor)是硬件执行指令的单元。线程(thread)是单一顺序控制流,是软件执行的具体化。线程的状态可以是运行中(running)(也称调度中(scheduled))、可运行(ready to run),或者是为等待某些条件而被阻塞(blocked),例如等待消息的到来、输入/输出的完成,或者到达特定的时间。调度器(scheduler)通常是操作系统组件,其功能是确定在任意时刻哪些线程应当在哪些处理器上执行。如果某个线程被调度器从某个处理器换出(其状态从运行中转变为可运行或者被阻塞),则当其下一次被调度时很可能会在另一个不同的处理器上运行。当然,调度器也允许线程和处理器之间存在一定的亲和性(affinity)。

某些处理器硬件支持多个逻辑处理器共用一条指令流水线,该技术称为同时多线程(simultaneous multithreading,SMT)或者超线程(hyperthreading)。这一概念会给我们的定义带来一定的麻烦。在我们的术语中,逻辑处理器通常被称为线程,但在此处,同时多线程处理器则可以看作是多(逻辑)处理器,并可以独立进行调度,因而线程这一概念便只能代表软件实体。

多处理器(multiprocessor)是包含多个处理器的计算机。片上多处理器(chip multiprocessor,CMP)是指在单个集成电路芯片上集成多个处理器的技术,也称多核处理器(multicore processor)甚至众核处理器(many-core processor)。抛开并发多处理器的概念不谈,多线程(multithread)是指使用多个线程的软件,且每个线程可能在多个处理器上并发运行。多程序(multiprogram)是指在单一处理器上执行多个进程或者线程的软件。

处理器与内存之间的互联

多处理器与集群计算、云计算或者分布式计算的区别在于,前者存在每个处理器都可以直接访问的共享内存。处理器对共享内存的访问需要以某种互联网络作为媒介。最简单的互联方式是处理器和内存之间使用单个共享总线(bus)来传递信息。我们可以简单地将内存访问操作看作是处理器和内存单元之间的消息通信,每次通信所需的时间可能会达到上百个处理器时钟周期。单个总线的原始速度相当快,但该速度在多处理器同时发起请求时却仍然会成为瓶颈。带宽最高的互联方式可能是在处理器和内存两两之间建立私有通道,但该方案所需的硬件资源却会正比于处理器和内存单元数量的乘积。为获取更高的整体带宽(整个系统中处理器和内存在一秒内可以传输的数据量,将内存分割成多个单元也是一种不错的方案。另外,处理器与内存之间的数据传输通常都是以高速缓存行而非单独的字或者字节为单位的。

对于更大的片上多处理器,一次内存访问请求在互联网络中的传递可能需要经过多个节点,例如当互联网络以网状或者环状方式组织时。此处的具体细节超出本书的讨论范围,但我们需要了解的是,内存的访问时间可能会随着处理器与内存单元在互联网络中的位置不同而发生变化。另外,相同互联路径上的并发访问也可能引发更大的延迟。

在单总线系统中,当处理器的数量达到8~16个之后,总线一般都会成为瓶颈。但相比其他互联方式,总线的实现通常更加简单且更加廉价,且总线允许每个单元侦听(listen)总线中的所有通信(有时也称为窥探(snoopIng),这可以简化系统对高速缓存一致性的支持。

如果内存单元与处理器之间相互独立,则该系统可以称为对称多处理器(symmetric multiprocessor,SMP)架构,该架构中每个处理器访问任意内存单元的时间都是相同的。我们同样也可以将内存与每个处理器相关联,此时处理器在访问与自身关联的内存时速度更快,而在访问与其他处理器关联的内存时则速度较慢。此类系统被称为非一致内存访问 (non-uniform memory access,NUMA)架构。同一系统可以同时包含全局的SMP内存以及NUMA内存,每个处理器还可以拥有私有内存,但共享内存与垃圾回收技术的关联更大。

对于处理器与内存之间的互联,最值得注意的地方是内存访问需要花费较长的时间,且互联网络可能成为系统的瓶颈,与此同时,不同处理器访问内存的不同部分可能会花费不同的时间。

内存

尽管内存在物理上可能会跨越多个内存单元或者处理器,但从垃圾回收器的角度来看,共享内存看起来就是一块由字或者字节组成的单个地址空间。由于内存是由多个可以并发访问的单元组成的,所以我们无法对其在任意时刻的状态给出一个全局性的描述,但是内存中的每个单元(也就是每个字)在每个时刻的状态都是确定的。

高速缓存

由于内存的访问速度如此之慢,所以现代体系架构通常会在处理器和内存之间增加一到多层高速缓存,其中所记录的是处理器最近访问过的数据,进而降低了程序运行期间处理器需要访问内存的次数。高速缓存与内存的数据交换是以高速缓存行(也称高速缓存块)为单位的,通常为32或者64字节。如果处理器在访问某一地址时发现其所需要的数据已经存在于高速缓存中,这一情况称为高速缓存命中(cache hit,反之则称高速缓存不命中(cache miss),此时处理器便需访问更高一级缓存,如果最高一级缓存依然不命中,则处理器必须访问内存。片上多处理器(CMP)中某些处理器可能会共享最高一级缓存,例如,每个处理器可能都拥有专属的L1高速缓存,但是其会与相邻的一个存储器共享L2高速缓存。各级高速缓存的缓存行大小可以不同。

当某一级缓存出现不命中,且该级缓存也无法容纳新的缓存行时,处理器就必须依照某种策略从中选择一个缓存行进行置换,被换出的缓存行称作受害者(victim)。当在缓存中写入数据时,某些缓存使用的是写通(write- through)策略,即当某一缓存行中的数据得到更新时,下一级缓存中的对应数据也会尽快得到更新。另一种策略是写回(write-back),即在被修改的行(也称脏行)得到换出之前其中的数据不会写入下一级缓存,除非进行显式刷新fush)(需要使用特殊的指令)或者显式写回(也需要特殊指令支持)。

缓存置换策略在很大程度上依赖于缓存的内部组织形式。全相联(fully- associative)缓存允许内存中任意地址的数据放置到缓存的任意一行中,其置换策略也可选择任意一行进行淘汰。与之对应的另一个极端是直接映射(direct-maped)缓存,即内存中某一地址的数据只能放置到缓存中特定的行,因而其置换策略只可能淘汰特定的缓存行。k路组相联(k-wayset- associative)缓存是上述两种极端方案的折中,该策略允许内存中特定地址的数据映射到缓存中的k个缓存行,其置换策略也可从这k个缓存行中选择一个进行淘汰。这三种基本的缓存置换策略还存在其他一些变种,例如受害者缓存(victim cache),该缓存包括一个使用直接映射策略的主缓存以及一个额外的容量较小的全相联缓存,从主缓存中淘汰的行将被置于全相联缓存中。该策略的缓存相联性较高,且硬件开销较小。

高速缓存设计中需要注意的另一方面是各级缓存之间的关系。对于相邻两级缓存,如果较低级别缓存中的数据一定会在高级别缓存中存在,则两级缓存为(严格)包容(inclusive)关系。相反,如果同一数据最多只能出现在两级缓存中的一级,则两级缓存为排他(exclusive)关系。真正的高速缓存设计也可进行折中,即允许同一行存在于两级缓存中,但也并不强制要求高级别缓存一定要包容低级别缓存的数据。

高速缓存一致性

高速缓存中所持有的数据在内存中很可能是共享的。由于每个缓存中的数据不可能同时得到更新(特别是对于使用写回策略的缓存),所以内存中同一地址的数据在不同缓存中的副本可能会出现不一致。因此,不同处理器在同一时刻读取同一地址的数据,可能会获得不同的结果,这显然是不应该出现的。为解决这一问题,底层硬件通常会提供一定级别的高速缓存一致性支持。一种经典的高速缓存一致性协议(coherence protocol)是MESI,在该协议中,每个缓存行可能有4种状态,这4种状态的首字母构成了该协议的名称。

被修改(modified):该缓存行持有数据的唯一有效副本,其中的数据被修改过,但尚未写回内存。
独占(exclusive):该缓存行持有数据的唯一有效副本,同时其中的数据与内存保持一致。
共享(shared):其他缓存行也可能持有数据的有效副本,同时所有副本中的数据均与内存保持一致。
无效(Invalide):缓存行中不包含任何有效数据。

只有当缓存行的状态为“被修改”、“独占”、“共享”其中之一时,处理器才可以读取该缓存行;只有当缓存行的状态为“被修改”或“独占”时,处理器才可以将数据写入该缓存行,写入之后其状态将成为“被修改”。如果处理器需要从“无效”缓存行中读取数据,则系统的后续行为取决于该缓存行在其他缓存中的状态:如果为“被修改”,则处理器必须将其写回内存,并将其状态置为“共享”(或者“无效”);如果状态为“独占”,则只需将其降级为“共享”(或“无效”);如果其状态为“共享”或者“无效”,则处理器只需简单地从内存或者其他缓存里状态为“共享”的缓存行中加载数据。如果处理器需要将数据写入“无效”缓存行中,系统的后续行为与读取时的行为类似,唯一的不同之处在于其他缓存行的最终状态都将是“无效”。如果处理器需要将数据写入“共享”缓存行中,其必须先将其他缓存行降级为“无效”。该协议可以进行的改进包括:以写为目的读可以在读取完成之后将其他缓存行的状态降级为“无效”;写回操作可以将缓存行的状态从“被修改”降级为“独占”;令某一缓存行失效的操作可以将状态为“被修改”的缓存行写回内存,然后将其状态置为“无效”。

MESI协议的关键之处在于,任意缓存行在同一时刻只能被一个处理器写,且两个缓存针对同一数据的缓存行永远不会产生不一致。MESI协议的实现难点在于,当处理器数量增大时算法的性能会下降,这也是所有由硬件支持的缓存一致性协议的共有问题。因此,更大的片上多处理器逐渐开始放弃内建的缓存一致性协议,转而开始由软件来管理一致性,此时软件便可选择任意类型的缓存一致性协议。即便如此,处理器数量增大时算法依然会存在性能问题,但与将算法固化在硬件中的策略相比,开发者至少可以根据其具体需求选择更好的致性算法。

缓存一致性要求引发了另一个问题,即伪共享(false sharing):当两个处理器同时访问并更新位于相同缓存行的不同数据时,由于处理器在写操作之前必须将缓存的状态更改为“独占”,所以两个处理器令对方缓存行失效的操作会产生“乒乓”效应,从而引发互联网络中大量的一致性通信,并可能引发额外的内存读取操作。

高速缓存一致性对性能的影响示例:自旋锁

典型的互斥锁可以通过AtomicExchange原语实现,如算法13.1所示。后续描述中我们均以首字母大写的方式来区分原子指令原语,我们同时也使用首字母小写的1oad和store来表示低级读写操作,并以此避免与应用程序和赋值器之间的读写接口混淆。锁的初始值应该为零,意味着未上锁。如果尝试加锁失败,处理器将在whie循环中自旋,因而称其为自旋锁。每次循环中,原子化的“读一修改-写”操作都会尝试独占其所在的高速缓存行,因而如果多处理器竞争该锁,高速缓存行将会出现“乒乓”效应,即使对于已经持有锁的处理器也不例外。更加糟糕的是,即使持有锁的处理器想要释放锁,其也需要与其他处理器竞争该高速缓存行的独占权。此种自旋锁实现方式被称为“检测并设置”锁(test-and- set lock)尽管它并未依赖我们后文将要介绍的 TestAndset原语。

// 算法13.1基于 AtomicExchange原语的自旋锁
exchangeLock(x):
	while AtomicExchange(x, 1)=1
	/*空*/

exchangeUnlock(x):
	*x <- 0

AtomicExchange(x, v):
	atomic
		old ← *X
		*x <- v
	return old

算法13.1所描述的自旋锁的实现方式会导致最严重的一种竞争情况出现,因而算法13.2所描述的“检测一检测并设置”锁(test-and-test-and-set lock)作为一种更加巧妙的改进版本,在许多程序中得到应用。其最大的改进之处在于第10行,算法在调用AtomicExchange方法之前先通过一般的读操作判断锁是否已被占用,因而此处的自旋操作只需访问处理器自身的(已经保持一致)的高速缓存,无需进一步访问总线。如果锁位于不可缓存(noncacheable)的内存中,则该线程可以使用空循环来等待,也可在检测之间插入硬件iale指令,如果等待时间稍长,则在两次检测之间的等待时间可以呈指数级别增加或者采用其他类似算法。如果等待时间过长,则线程可以请求操作系统的调度器介入并放弃剩余时间片,或者转而采取等待某一显式信号的方式,此时便要求锁的持有者在释放锁时发送信号。

//算法13.2基于AtomicExchange原语的“检测一检测并设置”自旋锁
testAndTestAndSetExchange Lock(x):
	while testAndExchange(x)=1
		/*空*/

testAndTestAndSetExchangeUnlock(x):
	*x <- 0

testAndExchange(x):
	while *x=1
	/*空*/
	return AtomicExchange(x, 1)

硬件内存一致性

我们假定共享内存可以提供与高速缓存相同的一致性(coherence)保障,即:不存在未完成的写操作。如果两个处理器读取内存中相同位置的值,所获取的值也是相同的。大多数硬件还可以进一步保证:如果两个处理器同时对内存的相同位置发起写操作,则其中的一个将先于另一个发生,同时所有处理器后续读取到的值都将是最后一次写入的值。另外,如果某一处理器已经读取到了最终的值,则在下一次写操作发生之前,其不可能读取到其他值。也就是说,针对内存中任何特定位置的写操作都是经过排序的,且在任意处理器看来,特定位置值的变化顺序都是相同的。

但是,对于程序在多个位置的写入(或者读取)操作,硬件系统却不能保证程序发起操作的顺序与其在高速缓存或者内存中的生效顺序完全一致,更不能保证其他处理器能够以相同的顺序感知到这些地址的数据变更。也就是说,程序顺序(program order)不一定要与内存顺序(memory order)完全一致。读者可能不禁会问:为何如此?其中的含义是什么?前一个问题关乎于硬件和软件,概括来讲,不要求两者完全一致是出于性能考虑—严格一致性(consistency)要么会耗费更多的硬件资源,要么会降低性能,或者两者兼有。对于硬件而言,许多处理器会使用写缓冲区(write buffer/store buffer)来保存未完成的内存写入操作。写缓冲区本质上是一个<地址,数据>对组队列。正常情况下,写操作可能会有序执行,但如果某一后发写操作的目的地址已经存在于写缓冲区中,则硬件可能会将其合并到队列里尚未完成的写操作中,这便意味着写操作可能会出现“后发先至”的情况,即较晚的写操作可能会越过较早的、针对其他地址的写操作而立即在内存中生效。处理器的设计者会小心地确保处理器操作针对其自身的一致性,也就是说,如果处理器在读取某一位置的值时发现该位置存在未完成的写操作,则处理器要么通过直接硬件路径(速度较快但开销较大)来读取该值,要么必须等写缓冲区刷新完毕后再从高速缓存中读取该值。另一个可能导致程序操作被重排序的原因是高速缓存不命中。一旦读取过程中发生高速缓存不命中,许多处理器会将其跳过并继续执行后续指令,进而可能出现后发读/写操作越过先发读/写操作先执行完毕的情况。另外,对于使用写回机制的高速缓存,其中的数据只有在被淘汰或者显式刷新时才会写入内存,因此针对不同缓存行的写操作的执行顺序可能会出现大幅度调整。上述各种硬件方面的原因只是说明性的,但并非面面俱到。

由软件产生的重排序大多是由编译器造成的。例如,如果编译器已知两个引用指向的是同一地址,且两个引用的读取操作之间并无其他写操作会影响该值,则编译器可能直接使用其第一次读取到的值优化掉第二次读操作。更一般的情况是,如果编译器可以确保各变量之间均不存在别名关系(即不引用相同的内存地址),则其可以对这些变量的读写操作以任意方式重排序,因为不论采用何种顺序,最终的执行结果都是相同的(对于单处理器而言,且假定不存在线程切换)。读取结果复用以及重排序策略可以产生更高效的代码,且在大多数情况下并不影响语义,因而许多编程语言都允许这一策略。

从开发者的角度来看,程序顺序与内存顺序之间缺乏一致性显然是一个潜在的问题,但是从硬件实现者的角度来看,如此设计可以大幅提升性能并减少开销。

放宽一致性要求将会产生怎样的后果?第一,这可能导致程序的执行完全背离开发者的意图,也可能导致在完全一致性模型下可正常执行的代码在更加复杂的一致性模型下产生混乱的执行结果。第二,锁相关等技术要求硬件以某种方式确保对不同地址的访问能够有序执行。各种顺序模型必须能够区别出3种主要的访问原语:读(read)、写( write)、原子(atomic)操作。原子操作需要原子化的“读一修改-写”原语,该原语通常是条件性的,例如TestAndset。内存一致性对于依赖加载(dependent load)也十分重要,所谓依赖加载,即程序需要先从地址x加载数据,然后再从地址y加载数据,但第二次加载操作的地址y取决于地址x的加载结果。依赖加载的一个典型案例是沿着指针链进行追踪。在完全一致性之外,还存在着许多较弱的内存访问顺序模型,我们将选择其中较为常见的进行介绍。

内存屏障与先于关系

内存屏障(memory fence)是一种处理器操作,它可以阻止处理器对某些内存访问进行重排序。特别地,它可以避免某些访问指令在屏障之前发送(issue),也可以避免某些访问指令被延迟到屏障之后发送,或者两者皆可。例如,完全读内存屏障可以确保屏障之前的所有读操作都能先于屏障之后的读操作执行。

先于关系(happens- before)这一概念则更加规范化,它是指内存访问操作在存储中所应遵从的发生顺序。完全读内存屏障相当于是在每两个相邻读操作之间施加了先于关系。原子操作通常会为其内部的所有子操作施加完全内存屏障:所有较早的读、写、原子操作都必须先于较晚的读、写、原子操作发生。在先于关系之外还存在其他一些模型,例如获取一释放(acquire-release)语义。在该模型下,获取操作(acquire operation)(可以将其看作是获取锁)能够阻止较晚操作在该操作之前发生,但较早的读写操作则可以在获取操作之后发生;释放操作(release operation)与之完全对称:它能够阻止较早的操作在释放操作之后发生,但是较晩的操作则可以在释放操作之前发生。简而言之,处理器可以将获取一释放操作对之外的操作移动到其内部,但却不能将其内部的操作移动到外部。临界区(critical section)便可使用获取一释放模型来实现。

内存一致性模型

最强的内存一致性模型当属严格一致性(strict consitency),即所有的读、写、原子操作在整个系统中的任意位置都以相同的顺序发生(occur)。严格一致性意味着所有操作的发生顺序都满足先于关系,且这一顺序是由某一全局时钟决定的。严格一致性是最容易理解的种模型,这可能也是大多数开发者以为硬件系统所遵从的顺序,但这一模型很难高效地实现。稍弱的一种模型是顺序一致性(sequential consistency)模型,在该模型中,全局先于顺序只需要与每个处理器的程序顺序保持一致即可。相对于其他更加宽松的一致性模型,顺序一致性模型下的编程更加简单,因而规模较小的处理器通常会尝试达到或者接近顺序一致性的要求。弱一致性(weak consitency)会将所有原子操作当作完全屏障。上文所描述的获取释放模型通常被称为释放一致性(release consitency)模型。因果一致性(causal consistency)模型的强度介于顺序一致性和弱一致性之间,该模型要求程序所发起的读操作与其后续的写操作之间必须满足先于关系,其目的在于避免读操作对写操作所写入的值造成影响,即对于先读取某个值然后再将其写入内存的操作,因果一致性会确保它们之间的先于关系。宽松一致性(relaxed consistency)模型泛指所有比顺序一致性模型更弱的模型。

硬件原语

比较并交换

即先判断内存地址的当前值,然后再尝试原子性地将其更新,该操作通常被称为“比较一比较并交换”(compare-then- compare-and-swap)。CompareAndSwap原语潜藏着一个微妙的陷阱,即在调用CompareAndSwap时,目标内存地址的值改变了数次,但该地址的当前值却与调用者之前获取到的值相等。某些情况下这可能不会出现问题,但在其他情况下,相同的值并不意味着相同的状态。例如在垃圾回收中,在经历两次半区复制回收之后,某一指针的目标对象很可能与其最初的目标对象完全不同。CompareAndswap原语无法探测到“某个值被修改,然后再被改回原值”的情况,即所谓的ABA问题(ABA problem)。

加载链接/条件存储

在LoadLinked和StoreConditionally原语中,处理器会记录LoadLinked原语所访问的地址,并使用处理器的一致性机制来探测所有针对该地址的更新操作,从而解决ABA问题。

LoadLinked/StoreConditionally原语还有另外一个特征需要注意:即使任何处理器都没有更新过保留地址的值, StoreConditionally原语也有可能出现假性失败。多种低级硬件状况可能导致假性失败,其中值得注意的是中断的出现,包括缺页陷阱、溢出陷阱、时钟中断、IO中断等,这些中断均需要由内核进行处理。这种失败通常不会成为问题,但是如果Loadlinked和StoreConditiona11y之间的某段代码总是引发陷阱,则StoreConditionallsy操作可能始终都会失败。

由于LoadLinked/StoreConditionally原语可以优雅地解决ABA问题,所以我们更加倾向于用其替代可能产生ABA问题的 CompareAndSwap原语。当然,我们也可为CompareAndswap原语关联一个计数器来解决ABA问题。

严格意义上讲,如果StoreConditionally原语所操作的并非之前保留的地址,则其最终结果可能是未定义的。但某些处理器在设计上便允许这种使用方式,这相当于提供了一种在某些场景下有用的、针对任意两个内存地址的原子操作。

原子算术原语

我们也可使用AtomicAdd或FetchAndAdd原语来实现 AtomicIncrement和AtomicDecrement操作,且其返回值既可以是原始值,也可以是新值。另外,处理器在执行这些原语时通常会设置条件码(condition code),其值可以用于反映目标地址的值是否为零(或者原始值为零),也可反映其他一些信息。在垃圾回收领域, FetchAndAdd原语可以用于实现并发环境下的顺序分配(即阶跃指针分配),但更好的做法通常是为每个线程建立本地分配缓冲区。FetchAndAdd可以简单地用于从队列中添加或者移除元素的操作,但是对于环状缓冲区,还需要小心地处理回绕(wrap-around)问题。

这些原子算术原语的能力严格弱于CompareAndswap,同时也弱于LoadLinked/StoreConditionally(参见Herlihy and Shavit)。每种原语都存在一个可以用一致数(consensus number)来描述的特征,如果某个原语的一致数为k,意味着它可以解决k个线程之间的一致问题,但无法解决多于k个线程之间的一致问题。所谓一致问题,是指多处理器算法是否能达到如下要求:

对于某个变量,每个线程均建议一个值;
所有线程针对某个值达成一致;
该变量的最终值为某个线程所建议的值;
所有线程均能够在有限步骤内完成操作,即算法必须满足无等待(wait-free)要求。

对于所有的无条件设置原语(例如AtomicExchange)或者对相同值产生相同运算结果的更新原语(如AtomicIncrement与FetchAndAdd),其一致数均为2。而CompareAndSwap和LoadLinked/StoreConditionally的一致数则为∞,即它们能够以无等待的方式解决任意多个线程之间的一致问题。

无条件算术原语的一个潜在优势在于它们通常都会成功,而如果使用CompareAndSwap或者LoadLinked/StoreConditionally来模拟无条件算术原语,线程之间的竞争很可能导致“饥饿”现象的出现。

更加强大的原语

在我们描述过的硬件原语中,LoadLinked/StoreConditionally的通用性最强,也是针对单字的最强的原子更新语义。除此之外,允许对多个独立字进行原子更新的硬件原语则更加强大。在单字原语之外,某些处理器还支持双字原语,例如双字比较并交换,我们称之为CompareAndSwapWide/CompareAndSetWide。如果仅从概念上来看,该原语的强大之处没得到充分体现。但是,使用双字CompareAndSwap操作却可以轻松应对单字CompareAndswap无法解决的ABA问题,此时我们只需要将第二个字用作记录第一个字被更新次数的计数器。对于32位的字,计数器的值最多可以达到2³²,因而基本上可以忽略计数器回绕可能带来的安全问题。支持对相邻两个64位的字进行原子更新的硬件原语则更加强大。因此,尽管CompareAndSwapWide在概念上与常规的CompareAndswap并无较大差别,但其在使用上却更加方便、更加高效。

尽管更新相邻两个字的原子操作原语十分有用,但如果其能够原子化地更新内存中任意两个(不相邻)字则会显得更加强大。 Motorola880000以及Sun的Rock处理器均提供了“双比较并交换”指令(compare-and-swap-two,也称double-compare-and-swap)。 CompareAndswap2的硬件实现较为复杂,因而目前尚无商业级别的处理器支持这一原语。 CompareAndSwap2可以泛化为通用的n路比较并交换(compare-and-swap-n,也称n-way-compare-and-swap),同理,也可对LoadLinkedStoreConditiona1ly原语进行泛化,由此得到的结果便是事务内存(transactional memory)。

原子操作原语的开销

开发者经常会错误地使用原子操作原语,其原因之一是他们知道原子操作的开销较大,因而会刻意避免使用原子操作,而另一种原因则是他们可能错误地使用了原子操作。我们曾经提到,有两个原因导致原子操作的开销较大:一是原子化的“读一修改一写”原语必须以独占方式访问相关的高速缓存行;二是在指令结束之前,处理器必须完成数据读取、计算新值、写入新值这一系列操作。现代处理器可能会使用多指令重叠(overlap)技术,但是如果后续操作强依赖于原子操作的结果,则必然会减少流水线中的指令条数。由于原子操作需要确保一致性,因而其通常会涉及总线甚至内存的访问,这通常会花费较多的指令周期。

另一个导致原子操作执行速度较慢的原因是,它们要么天然包括内存屏障语义,要么要求开发者在其开始和结束位置手动添加额外的内存屏障。这潜在削减了指令重叠与流水线技术所带来的性能优势,从而导致处理器很难隐藏这些原语访问总线或者内存的开销。

前进保障

当多个线程之间竞争相同数据结构时(例如共享堆,或者回收器数据结构),确保整个系统能够正常往下执行尤为重要(特别是在实时环境中),我们将这一要求称为前进保障(progress guarantee)。了解不同硬件原语在前进保障方面的相对强度也十分必要,常见的前进保障级别从强到弱分别是:无等待、无障碍、无锁。对于并发算法而言,如果每个线程始终都可以向前执行(不论其他线程执行何种操作),则称其为无等待(wait-free)算法;如果在并发算法中,对于任意一个线程,只要其拥有足够长的独占式执行时间,便能够在有限步骤内完成操作,则称该算法为无障碍(obstruction-free)算法;如果算法永远可以保证某些线程能在有限步骤内完成操作,则称该算法为无锁(lock-free)算法。在真实系统中,前进保障通常是条件性的,例如,某一算法满足无等待要求的条件可能是存储空间尚未耗尽。Herlihy和Shavit对这些概念及其实现进行了详尽的论述。

无等待算法通常会引入线程互助的概念,也就是说,如果线程t2即将执行的操作可能会打断线程t1正在执行的、在一定程度上可以确定超前于线程n的操作,则线程t2将协助t1完成其工作,然后再开始执行自身工作。假设线程数量存在固定上界,且线程之间相互协助的工作单元或者对数据结构的操作也存在上界,则任何工作单元或者操作的完成步骤便都存在上界。但是,这一上界通常较大,且与较弱的前进保障相比,线程互助需要引入额外的数据结构与工作量,因而其操作时间通常相当长。对于较为简单的一致性场景,为其设计时间开销较小的无等待算法通常比较容易。从中我们可以看出,该算法满足解决N个线程的一致问题的所有标准,但是其空间开销正比于N。

与无等待要求相比,无障碍更容易实现,但是其可能需要调度器的协助。如果线程发现当前存在竞争,则它可以使用随机递增的时间退让策略来确保其他线程优先完成工作。也就是说,每当线程探测到竞争时,其首先会计算一个比上次退让时间更长的时间周期T,然后再从0~T之间选择某一随机值作为本次退让的时间。从概率上讲,对于较少出现竞争的场景,每个线程最终都会成功执行。

无锁要求的实现则更加简单,它只要求在任何情况下至少一个竞争者可以继续往下执行,即使其他线程可能会永久性地等待下去。

工作共享与结束检测

汇聚屏障

并发回收或者并行回收中另一种常见的同步机制是要求所有回收线程到达算法的某点(基本上就是某一回收阶段的结束点),然后再继续往下执行。一般情况下,上述任意种结束检测算法都可以胜任这一场景的要求。另一种常见的场景是:算法在某一阶段的工作并不存在任何形式的工作共享或者负载均衡,但其仍要求所有线程都到达指定点,即汇聚屏障(rendezvous barrier)。

并发数据结构

有多种通用实现策略可供开发者在构建并发数据结构时选择,这些策略在并发程度方面从最低到最高(通常也是从最简单到最复杂)分别如下:

粗粒度锁(coarse-grained locking):使用一个“大”锁来控制整个数据结构的访问。
细粒度锁(fine-grained locking):该方案为较大数据结构中的每个元素维护独立的锁,例如为链表或树中的每个节点维护一个锁。如果各线程对数据结构的访问与更新足够分散,则该策略可以显著提升并发程度。该策略通常需要考虑一个问题,即如果某一操作会对多个元素加锁,则其必须保证没有其他相同操作(或者任何其他操作)会以相反的顺序对相同元素进行加锁,否则将导致死锁的产生。一种通用的解决方案是要求所有操作在访问(单链表或者树中的)元素时遵从相同的方向,即锁联结(lock coupling):某一操作先对节点A加锁,然后再对A所指向的节点B加锁,接着再释放节点A的锁并对节点B所指向的节点C加锁,以此类推。使用这一逐步推进策略来遍历数据结构可以确保后发线程无法超越先发的线程,同时也可以确保在链表/树中插入/删除元素操作的安全性。细粒度锁的一个潜在缺陷是,对不同元素多次加解锁可能会给共享总线或者存储带来一定开销,进而掩盖了相对于粗粒度锁的优势。
乐观锁(optimistic locking):该方案对细粒度锁进行了改进,即线程在对数据结构进行遍历时先不加锁,直到其找到合适元素时才尝试对其进行加锁。但在从发现合适元素到加锁成功的过程中,该元素可能已被其他并发线程修改,因而线程在加锁完成后需要再次对该元素进行校验。如果校验失败,则其需要释放锁并继续查找。这种尽量将加锁操作延迟、直到迫不得已时才加锁的策略可以减少开销并提升并发能力。乐观锁在大多数场景下都具有较高的性能,但如果频繁发生更新冲突,
懒惰更新(lazy update):即使采用乐观锁,只读操作仍需要对其所读取的元素加锁,这不仅会成为提升并发程度的瓶颈,还可能在只读操作中引入写操作(即加解锁)。为此我们可以设计出一种数据结构,在该结构中只读操作无需加锁,代价是更新操作的复杂度稍有提高。一般来讲,懒惰更新策略中的写操作需要先达到其在“逻辑上”的目标(前提是不影响其他线程的并发访问),然后再进一步执行真正的更新操作,并确保数据结构回归正常状态。我们可以通过一个例子来理解懒惰更新的含义:对于以链表方式实现的集合, remove操作首先需要(在逻辑上)将待移除元素打上deleted标记,然后再将其前一个节点的指针重定向从而真正实现节点的移除。为避免并发更新可能带来的问题,所有操作都需要在持有相关元素锁的前提下执行。remove操作必须依照先标记再移除的顺序执行,这样才能确保其他线程能够在不加锁的情况下正确进行读操作。向链表中插入元素的操作只需要更新数据结构中的next指针,因而只需要一次更新操作(即无需事先设置标记),当然,这一操作同样必须在持有相关元素锁的前提下执行。
非阻塞(non-blocking):在非阻塞策略中,对数据结构的所有操作均无需使用锁,仅依赖原子更新原语便可完成数据结构的状态变更。一般来说,状态变更操作通常都会存在某些特殊的原子更新事件,这些事件的发生点即为该操作的线性化点。与此相比,基于锁的策略则需要引入临界区来标识线性化“点”。非阻塞策略的并发能力可以通过前进保障来衡量,无锁实现可能允许部分线程出现饥饿;无障碍实现中的每个线程可能需要足够长的时间进行独占式操作,才能确保算法整体往下执行;无等待实现可以确保所有线程都能正确往下执行。

需要考虑的问题

平台支持哪些原子更新原语?尽管LoadLinked/StoreConditionally原语便于使用且更加高效,但大多数流行系统仅支持 CompareAndSwap或者等价原语,后者可能会遇到ABA问题,但该问题也可通过某种方式来避免。或许在不久的将来,事务内存将逐渐实用化。

算法需要达到何种级别的前进保障要求?较弱的前进保障更容易实现,也更易于推导。对于访问量较低的数据结构,直接进行加锁可能会更加合适,因为与具有更强前进保障级别的无锁算法相比,加锁不仅容易实现,而且更容易正确地实现。另外,即使在某些已发布的、绝大多数场景满足无等待要求的系统中,某些极端情况的处理仍会使用更加简单的实现技术,将这些非关键场景无等待化并不具有太大价值。

并行垃圾回收

并行垃圾回收分类

不论是对于哪种情况,我们均需要关注算法如何实现回收工作的获取(acquire)、执行(perform)、生成(generate),这3种操作的设计与实现决定了算法所需同步操作的类型、单个回收线程的负载粒度,以及在多个处理器之间进行负载均衡的策略行垃圾回收算法大致可以划分为两大类,即以处理器为中心(processor-centric)的并行算法和以内存为中心(memory- centrIc)的并行算法。在以处理器为中心的算法中,线程所获取的工作通常大小不等,且线程之间通常会存在工作窃取行为。该策略通常不关注线程所处理对象的位置,但通过前面的章节我们知道,即使是在单处理器环境下,局部性都会对处理性能产生显著影响,而对于非一致内存或者异构系统而言,局部性的作用则更加重要。以内存为中心的算法会更多考虑局部性因素,此类算法通常会针对堆中连续内存块进行操作,并从共享工作缓冲区池中获取工作包(或者将工作包释放到全局工作池中),工作包的大小通常固定。绝大多数并行复制式回收器均使用这一策略。

最后让我们关注并行回收的结束。回收线程不仅会尝试获取工作,而且还会进一步动态地生成新的工作。因此,简单判定共享工作池是否为空通常不足以断定回收过程是否结束,因为活动线程可能还会向工作池中加入新的任务。

14章及以后，只是泛读了一下